package leetcode.sort;

import java.util.Arrays;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/14 18:22
 * @description :
 */
public class HeapSort {

    public static void main(String[] args) {
        int N = 8;
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int)(Math.random() * 100);
        }
        System.out.println(Arrays.toString(arr));
        //构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0 ; i--) {
            adjust(arr, i, arr.length);
        }
        //将堆顶元素与末尾元素进行交换，然后重新调整大顶堆
        for(int i = arr.length - 1; i >= 0; i--) {
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            adjust(arr, 0, i);
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            adjust(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            adjust(arr, 0, i);
        }
    }

    public static void adjust(int[]arr, int parentIndex, int len) {
        int temp = arr[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < len) {
            if (childIndex + 1 < len && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
            if (temp >= arr[childIndex]) break;
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        arr[parentIndex] = temp;
    }
}
